package com.leetcode.partition2;

/**
 * @author `RKC`
 * @date 2021/8/23 18:47
 */
public class LC188买卖股票的最佳时机4 {

    public static int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;
        return dynamicProgramming(k, prices);
    }

    public static void main(String[] args) {
        int k = 2;
        int[] prices = {3, 2, 6, 5, 0, 3};
        System.out.println(maxProfit(k, prices));
    }

    private static int dynamicProgramming(int k, int[] prices) {
        //根据123题推导
        int[][] dp = new int[prices.length][2 * k + 1];
        dp[0][0] = 0;
        for (int i = 1; i < dp[0].length; i++) {
            if (i % 2 == 0) dp[0][i] = 0;
            else dp[0][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j < dp[0].length; j++) {
                if (j % 2 == 0) dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);
                else dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
            }
        }
        return dp[prices.length - 1][2 * k];
    }
}
